class Solution {
public:
    void InOrder(TreeNode* root, vector<TreeNode*>& v)
    {
        if (root == nullptr)
            return;
        InOrder(root->left, v);
        v.push_back(root);
        InOrder(root->right, v);
    }
    TreeNode* increasingBST(TreeNode* root) {
        vector<TreeNode*> v;
        InOrder(root, v);
        while (root->left)
            root = root->left;
        TreeNode* newroot = root;
        for (auto& e : v)
        {
            newroot->right = e;
            newroot = newroot->right;
            newroot->left = nullptr;
        }
        newroot->right = nullptr;
        return root;
    }
};